package com.ss;

/**
 * range-sum-query-immutable
 * 区域和检索 - 数组不可变
 *  给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
 *  （要求调用方法次数级为 10^4 次）
 * @author 叁昇
 * @create 2021-03-01-18:48
 */
public class Leetcode_303 {
    static class NumArray {
        int[] sums; // 使用前缀和进行预处理

        public NumArray(int[] nums) {
            int n = nums.length;
            sums = new int[n+1];
            for (int i = 0; i < n; i++) {
                sums[i+1] = sums[i] + nums[i];
            }
        }

        public int sumRange(int i, int j){
            return sums[j+1] - sums[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = { -2, 0, 3, -5, 2, -1 };
        NumArray numArray = new NumArray(arr);
        System.out.println(numArray.sumRange(0, 2));; // return 1 ((-2) + 0 + 3)
        System.out.println(numArray.sumRange(2, 5)); // return -1 (3 + (-5) + 2 + (-1))
        System.out.println(numArray.sumRange(0, 5)); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
    }
}
